#include <stdlib.h>
#include <time.h>
#include <stdio.h>
#include "heapcomm.h"

#define MAX_ARRAY_SIZE 100
#define MIN_PRIORITY 0

int curLen = 10;


elem maximum(elem queue[]){
    if(curLen==0){
        printf("no element in queue!\n");
        return -1;
    }else{
        return queue[1];
    }
}

elem extract_maximum(elem queue[]){
    if(curLen==0){
        printf("no element in queue!\n");
        return -1;
    }else{
        queue[0]=queue[1];
        queue[1]=queue[curLen];
        curLen--;
        max_heapify(queue,1,curLen);
        return queue[0];
    }
}

void increase_key(elem queue[],int index,elem key){
    if(index<1||index>curLen){
        printf("error index!\n");
    }
    if(key<=queue[index]){
        printf("key must bigger than %d\n",queue[index]);
    }
    queue[index] = key;
    int parent = 0;
    while(index>1){
        parent = index%2;
        if(parent==0){
            parent = index/2;
        }else{
            parent = (index-1)/2;
        }
        if(queue[parent]<queue[index]){
            queue[0] = queue[parent];
            queue[parent] = key;
            queue[index] = queue[0];
            index = parent;
        }else{
            break;
        }
    }
}

void insert(elem queue[],elem x){
    if(curLen==MAX_ARRAY_SIZE){
        printf("queue is full!\n");
    }
    queue[++curLen] = MIN_PRIORITY;
    increase_key(queue,curLen,x);
}

int main(){
    int i = 0;
    int queue[MAX_ARRAY_SIZE+1];
    srand((unsigned)time(NULL));

    for(i=1;i<=curLen;i++){
        queue[i] = rand()%1000;
    }
    build_max_heap(queue,curLen);

    printf("queue [");
    for(i=1;i<=curLen;i++){
        printf("%d",queue[i]);
        if(i<curLen){
            printf(",");
        }
    }
    printf("] \n");

    printf("maximum is %d\n",maximum(queue));

    extract_maximum(queue);

    printf("extracted queue [");
    for(i=1;i<=curLen;i++){
        printf("%d",queue[i]);
        if(i<curLen){
            printf(",");
        }
    }
    printf("] \n");

    increase_key(queue,5,300);

    printf("increased queue [");
    for(i=1;i<=curLen;i++){
        printf("%d",queue[i]);
        if(i<curLen){
            printf(",");
        }
    }
    printf("] \n");

    insert(queue,500);

    printf("inserted queue [");
    for(i=1;i<=curLen;i++){
        printf("%d",queue[i]);
        if(i<curLen){
            printf(",");
        }
    }
    printf("] \n");

    return 0;
}


